Meeting Pearls 1/Meeting Pearls Vol 1 (1994).iso/installed_progs/text/faqs/nonlinear-programming-faq

Internet Message Format | 1994-05-04 | 21.7 KB

Subject: Nonlinear Programming FAQ
Newsgroups: news.answers,sci.answers,sci.op-research
From: [e-mail] (John Gregory)
Date: 2 May 94 16:22:11 CDT

Posted-By: auto-faq 2.4
Archive-name: nonlinear-programming-faq
Last-modified: May 1, 1994

        Nonlinear Programming - Frequently Asked Questions List
                      (nonlinear-programming-faq)
           Posted monthly to Usenet newsgroup sci.op-research
                 Most recent update: May 1, 1994

-----------------------------------------------------------------------

"Happiness is having a scratch for every itch."  -- Ogden Nash

Q0.  "What's in this FAQ?"

A:  Table of Contents
   Q1.  "What is Nonlinear Programming?"
   Q2.  "What software is there for nonlinear optimization?"
   Q3.  "I wrote an optimization code.  Where are some test models?"
   Q4.  "What references are there in this field?"
   Q5.  "How do I access the Netlib server?
   Q6.  "Who maintains this FAQ list?"

See also the related FAQ on Linear Programming (LP).

-----------------------------------------------------------------------

Q1.  "What is Nonlinear Programming?"

A:  A Nonlinear Program (NLP) is a problem that can be put into the
form

    minimize   F(x)
    subject to g (x)  = 0     for i=1,...,m1       where m1 >= 0
                i
               h (x) >= 0    for j=m1+1,...,m      where m >= m1
                j

That is, there is one scalar-valued function F, of several variables (x
here is a vector), that we seek to minimize subject (perhaps) to one or
more other such functions that serve to limit or define the values of
these variables.  F is called the "objective function", while the
various other functions are called the "constraints".  (If maximization
is sought, it is trivial to do so, by multiplying F by -1.)

Because NLP is a difficult field, researchers have identified special
cases for study.  A particularly well studied case is the one where
all the constraints g and h are linear.  The name for such a problem,
unsurprisingly, is "linearly constrained optimization".  If, as well,
the objective function is quadratic at most, this problem is called
Quadratic Programming (QP).  A further special case of great importance
is where the objective function is entirely linear; this is called
Linear Programming and is discussed in a separate FAQ list.  Another
important special case, called unconstrained optimization, is where
there are no constraints at all.

One of the greatest challenges in NLP is that some problems exhibit
"local optima"; that is, spurious solutions that merely satisfy the
requirements on the derivatives of the functions.  Think of a near-
sighted mountain climber in a terrain with multiple peaks, some peaks
higher than others, and you'll see the difficulty posed for an
algorithm that tries to move from point to point only by climbing
uphill.  Algorithms that propose to overcome this difficulty are termed
"Global Optimization".

The word "Programming" is used here in the sense of "planning"; the
necessary relationship to computer programming was incidental to the
choice of name.  Hence the phrase "NLP program" to refer to a piece of
software is not a redundancy, although I tend to use the term "code"
instead of "program" to avoid the possible ambiguity.

-----------------------------------------------------------------------

Q2.  "What software is there for nonlinear optimization?"

A: It's unrealistic to expect to find one general NLP code that's going
to work for every kind of nonlinear model.  Instead, you should try to
find a code that fits the problem you are solving.  If your problem
doesn't fit in any category except "general", or if you insist on a
globally optimal solution (except when there no chance of encountering
multiple local optima), you should be prepared to have to use a method
that boils down to exhaustive search, i.e., you have an intractable
problem.

I would be extremely interested in hearing of people's experiences with
the codes they learn about from reading this FAQ.  (Note, I'm looking
for more-or-less independent confirmation or denial of the practicality
of codes.)

Several of the commercial LP codes referenced in the LP FAQ have
specialized routines, particularly QP.  The ones that I know of that
have some form of QP are: LINDO, KORBX, LOQO, MPS-III, OSL, and
PC-PROG.  Many general nonlinear problems can be solved (or at least
confronted) by application of a sequence of LP or QP approximations.

There are ACM TOMS routines for QP, #559 and #587, available from the
netlib server, in directory /netlib/toms.

There is a directory, /netlib/opt, on the netlib server containing a
collection of optimization routines.  The last time I checked, I saw
- "praxis" (unconstrained optimization, without requiring derivatives)
- "tn" (Newton method for unconstrained or simple-bound optimization)
- "ve08" (optimization of unconstrained separable function).
- "simann" (unconstrained optimization using Simulated Annealing)
- "subplex"(unconstrained optimization, general multivariate functions)
- "donlp" (differentiable nonlinear optimization, dense linear algebra)
- "hooke" (Hooke and Jeeves method)

For nonlinear optimization problems with both continuous and binary
variables (MINLP), there is a code called DICOPT++, available
commercially from GAMS Development Corp.  Contact [e-mail] for
more information.

For difficult problems like Global Optimization, methods like Genetic
Algorithms and Simulated Annealing have been studied heavily.  I'm not
well-versed in any of these topics, and I have been assured of
contradictory things by different experts.  A particular point of
controversy is whether there is a proof of optimality for practical
variants of such algorithms for Global Optimization problems, and I
take no particular stand on the issue (since for difficult problems
such a proof may be of academic interest only).  Even moreso than
usual, I say "let the user beware" when it comes to code.  There's a
(compressed) Postscript file available by anonymous FTP, containing a
forty-page introduction to the topic of GA, that one can obtain from
beethoven.cs.colostate.edu in file pub/TechReports/1993/tr-103.ps.Z.
The Usenet newsgroup on GA, comp.ai.genetic, has a FAQ on the topic,
otherwise known as "The Hitch-Hiker's Guide to Evolutionary
Computation".  That FAQ can be obtained by anonymous FTP at
rtfm.mit.edu, in directory /pub/usenet/news.answers/ai-faq/genetic,
in files named part* .  Genetic Algorithm code can be obtained from
cs.ucsd.edu in /pub/GAucsd.  Simulated Annealing code for NLP and other
problems is available at ftp.alumni.caltech.edu, /pub/ingber - contact
Lester Ingber ([e-mail]) for more info.  I am unaware
of the existence of any other widely available and "ready-to-use"
software for finding answers to Global Optimization problems.  For
other ideas on Global Optimization, you may want to consult one of the
books given in the section on references, such as [Nemhauser] or one of
the ones with "Global" in its title.  There is also a Journal of Global
Optimization, published by Kluwer.

Here is a summary of other NLP codes mentioned in newsgroups in the
past few years, sorted alphabetically.  Perhaps someone will volunteer
to organize these references more usefully.

- Amoeba - Numerical Recipes
- Brent's Method - Numerical Recipes
- CONMIN - Vanderplaats and Associates, Goleta CA
- CONOPT - large-scale GRG code, by Arne Drud.  Available with GAMS
  or AMPL (modeling languages) or standalone.
- DFPMIN - Numerical Recipes  (Davidon-Fletcher-Powell)
- Eureka - Borland Software (for IBM PC class of machines)
- FSQP/CFSQP (Fortran/C) -  Contact Andre Tits, [e-mail].
  Free of charge to academic users.  Solves general nonlinear
  constrained problems, including constrained minimax problems.  CFSQP
  (C code) includes a scheme to efficently handle problems with many
  constraints (e.g., discretized semi-infinite problems).
- GENOCOP - Solves linearly constrained problems via a Genetic
  algorithm, available by FTP at unccsun.uncc.edu (152.15.10.88).
  Author: Zbigniew Michalewicz, [e-mail].
- GINO - LINDO Systems, Chicago, IL
- GRG2 - Leon Lasdon, University of Texas, Austin TX
- Harwell Library routine VF04.
- Hooke and Jeeves algorithm - see reference below.  A version is
  available from netlib, in /netlib/opt/hooke.c, and may be useful
  because it handles nondifferentiable and/or discontinuous functions.
- IMSL routine UMINF and UMIDH.
- LANCELOT - large scale NLP. See the book by Conn et al. in the
  references section.  For peaceful purposes only.
- LSSOL - Stanford Business Software Inc.  (See MINOS)
  This code does convex (positive semi-definite) QP.  Is the QP solver
  used in current versions of NPSOL.
- MATLAB Optimization Toolbox - The Mathworks, Inc. 508-653-1415.
  Handles various nonlinear optimization problems.
  Data sheet available in postscript format via anonymous FTP:
  ftp.mathworks.com in /pub/product-info/optimization.ps .
  Email address: [e-mail] .
- MINOS - Stanford Business Software Inc., 415-962-8719.  Mailing
  address: 2672 Bayshore Parkway, Suite 304, Mountain View, CA 94043.
  This code is often used by researchers as a "benchmark" for others
  to compare with.
- MINPACK I and II - Contact Steve Wright, [e-mail], or
  check the netlib server.
- NAG Library routine E04UCF (essentially the same as NPSOL).
- NOVA - DOT Products, Houston TX
- NPSOL - Stanford Business Software Inc.  (See MINOS)
- QLD - Contact: [e-mail].  Solves Quadratic
  Programming and other nonlinear problems.
- QPSOL - see LSSOL.

A book that became available in November 1993 is the "Optimization
Software Guide," by Jorge More and Stephen Wright, from SIAM Books.
Call 1-800-447-7426 to order ($24.50, less ten percent if you are a
SIAM member).  It contains references to 75 available software
packages, and goes into more detail than is possible in this FAQ.

-----------------------------------------------------------------------

Q3.  "I wrote an optimization code.  Where are some test models?"

A: There are various test sets for NLP.  Among those I've seen
mentioned are:
  - A. Corana et al, "Minimizing Multimodal Functions of Continuous
    Variables with the Simulated Annealing Algorithm," ACM Transactions
    on Mathematical Software, Vol. 13, No. 3, Sept 1987, pp. 262-280.
    (Difficult unconstrained nonlinear models)
  - C.A. Floudas and P.M. Pardalos, A Collection of Test Problems for
    Constrained Global Optimization Algorithms, Springer-Verlag,
    Lecture Notes in Computer Science 455 (1990).
  - W.W. Hager, P.M. Pardalos, I.M. Roussos, and H.D. Sahinoglou,
    Active Constraints, Indefinite Quadratic Programming, and Test
    Problems, Journal of Optimization Theory and Applications Vol. 68,
    No. 3 (1991), pp. 499-511.
  - J. Hasselberg, P.M. Pardalos and G. Vairaktarakis, Test case
    generators and computational results for the maximum clique
    problem, Journal of Global Optimization 3 (1993), pp. 463-482.
  - B. Khoury, P.M. Pardalos and D.-Z. Du, A test problem generator for
    the steiner problem in graphs, ACM Transactions on Mathematical
    Software, Vol. 19, No. 4 (1993), pp. 509-522.
  - Y. Li and P.M. Pardalos, Generating quadratic assignment test
    problems with known optimal permutations, Computational
    Optimization and Applications Vol. 1, No. 2 (1992), pp.  163-184.
  - P. Pardalos, "Generation of Large-Scale Quadratic Programs", ACM
    Transactions on Mathematical Software, Vol. 13, No. 2, p. 133.
  - P.M. Pardalos, Construction of test problems in quadratic bivalent
    programming, ACM Transactions on Mathematical Software, Vol. 17,
    No. 1 (1991), pp. 74-87.
  - P.M. Pardalos, Generation of large-scale quadratic programs for use
    as global optimization test problems,  ACM Transactions on
    Mathematical Software, Vol. 13, No. 2 (1987), pp. 133-137.
  - F. Schoen, "A Wide Class of Test Functions for Global
    Optimization", J. of Global Optimization, 3, 133-137, 1993, with
    C source code available for anonymous FTP at ghost.dsi.unimi.it,
    directory ftp/pub/schoen.
  - publications (referenced in another section of this list) by
    Schittkowski; Hock & Schittkowski; Torn & Zilinskas.
Some of the other publications listed in the references section also
may contain problems that you could use to test a code.

A package called CUTE (Constrained and Unconstrained Testing
Environment) is a set of Fortran subroutines, system tools and test
problems in the area of nonlinear optimization and nonlinear equations.
The package may be obtained via anonymous FTP at camelot.cc.rl.ac.uk
(Internet 130.246.8.61), in the directory pub/cute, or at
thales.math.fundp.ac.be (Internet 138.48.4.14) in directory cute.  A
LaTex formatted manuscript is included in the distribution file.
Download the README file first and follow the directions contained
therein.  Questions should be directed toward any of the package's
authors:
  Ingrid Bongartz     [e-mail]
  Andy Conn           [e-mail]
  Nick Gould          [e-mail]
  Philippe Toint      [e-mail]

John Beasley has posted information on his OR-Lib, which contains
various optimization test problems.  Send e-mail to
[e-mail] to get started.  Or have a look in the
Journal of the Operational Research Society, Volume 41, Number 11,
Pages 1069-72.  The only nonlinear models in this collection at this
writing are Quadratic Assignment problems.

The modeling language GAMS comes with about 150 test models, which you
might be able to test your code with.  The models are in the public
domain according to the vendor, although you need access to a GAMS
system if you want to run them without modifying the files.

In the journal Mathematical Programming, Volume 61 (1993) Number 2,
there is an article by Calamai et al. that discusses how to generate QP
test models.  It gives what seems a very full bibliography of earlier
articles on this topic.  The author offers at the end of the article to
send a Fortran code that generates QP models, if you send email to
[e-mail].

The paper "An evaluation of the Sniffer Global Optimization Algorithm
Using Standard Test Functions", Roger A.R. Butler and Edward E.
Slaminka, J. Comp. Physics, 99, 28-32, (1992) mentions  the following
reference containing 7 functions that were intended to thwart global
minimization algorithms: "Towards Global Optimization 2", L.C.W. Dixon
and G.P. Szego, North-Holland, 1978.
[from Dean Schulze - [e-mail]]

-----------------------------------------------------------------------

Q4.  "What references are there in this field?"

A:  What follows here is an idiosyncratic list, a few books that I like
or have been recommended on the net.  I have *not* reviewed them all.

General reference
-  Nemhauser, Rinnooy Kan, & Todd, eds, Optimization, North-Holland,
   1989.  (Very broad-reaching, with large bibliography.  Good
   reference; it's the place I tend to look first.  Expensive, and
   tough reading for beginners.)

Other publications (can someone help classify these more usefully?)
-  Bazaraa & Shetty, Nonlinear Programming, Theory & Applications.
-  Coleman & Li, Large Scale Numerical Optimization, SIAM Books.
-  Conn, A.R., et al., "LANCELOT: A code for large-scale, constrained,
   NLP", Springer series in computational mathematics, 1992.
-  Dennis & Schnabel, Numerical Methods for Unconstrained Optimization
   and Nonlinear Equations, Prentice Hall, 1983.
-  Fiacco & McCormick, Sequential Unconstrained Minimization
   Techniques, SIAM Books.  (An old standby, given new life by the
   interior point LP methods.)
-  Fletcher, R., Practical Methods of Optimization, Wiley, 1987.  (Good
   reference for Quadratic Programming, among other things.)
-  Floudas & Pardalos, Recent Advances in Global Optimization,
   Princeton University Press, 1992.
-  Gill, Murray & Wright, Practical Optimization, Academic Press, 1981.
   (An instant NLP classic when it was published.)
-  Himmelblau, Applied Nonlinear Programming, McGraw-Hill, 1972.
   (Contains some famous test problems.)
-  Hock & Schittkowski, Test Examples for Nonlinear Programming Codes,
   Springer-Verlag, 1981.
-  Hooke & Jeeves, "Direct Search Solution of Numerical and Statistical
   Problems", Journal of the ACM, Vol.8 pp. 212-229, April 1961.
-  Horst and Tuy, Global Optimization, Springer-Verlag, 1993.
-  Kahaner, Moler & Nash, Numerical Methods and Software, Prentice-
   Hall.
-  Luenberger, Introduction to Linear and Nonlinear Programming,
   Addison Wesley, 1984.  (Updated version of an old standby.)
-  More, "Numerical Solution of Bound Constrained Problems", in
   Computational Techniques & Applications, CTAC-87, Noye & Fletcher,
   eds, North-Holland, 29-37,  1988.
-  More & Toraldo, Algorithms for Bound Constrained Quadratic
   Programming Problems, Numerische Mathematik 55, 377-400, 1989.
-  More & Wright, "Optimization Software Guide", SIAM, 1993.
-  Nocedal, J., summary of algorithms for unconstrained optimization
   in "Acta Numerica 1992".
-  Schittkowski, Nonlinear Programming Codes, Springer-Verlag, 1980.
-  Schittkowski, More Test Examples for Nonlinear Programming Codes,
   Lecture Notes in Economics and Math. Systems 282, Springer 1987.
-  Torn & Zilinskas, Global Optimization, Springer-Verlag, 1989.
-  Wright, M., "Interior methods for constrained optimization", Acta
   Mathematica, Cambridge University Press, 1992.  (Survey article.)

Simulated Annealing & Genetic Algorithms
-  Davis, L. (ed.), Genetic Algorithms and Simulated Annealing, Morgan
   Kaufmann, 1989.
-  De Jong, "Genetic algorithms are NOT function optimizers" in
   Foundations of Genetic Algorithms: Proceedings 24-29 July 1992, D.
   Whitley (ed.) Morgan Kaufman
-  Goldberg, D., "Genetic Algorithms in Search, Optimization, and
   Machine Learning", Addison-Wesley, 1989.
-  Ingber "Very fast simulated re-annealing" Mathematical and Computer
   Modeling, 12(8) 1989, 967-973
-  Kirkpatrick, Gelatt & Vecchi, Optimization by Simulated Annealing,
   Science, 220 (4598) 671-680, 1983.
-  Michalewicz et al., article in volume 3(4) 1991 of the ORSA Journal
   on Computing.
-  Michalewicz, Z., "Genetic Algorithms + Data Structures = Evolution
   Programs", Springer Verlag, 1992.
-  Reeves, C.R., ed., Modern Heuristic Techniques for Combinatorial
   Problems, Halsted Press (Wiley).  (Contains chapters on tabu search,
   simulated annealing, genetic algorithms, neural nets, and Lagrangean
   relaxation.)

-----------------------------------------------------------------------

Q5.  "How do I access the Netlib server?

A:  If you have FTP access, you can try "ftp netlib2.cs.utk.edu", using
"anonymous" as the Name, and your email address as the Password.  Do a
"cd <dir>" where <dir> is whatever directory was mentioned, and look
around, then do a "get <filename>" on anything that seems interesting.
There often will be a "README" file, which you would want to look at
first.  Another FTP site is "netlib.att.com", although you will first
need to do "cd netlib" before you can cd to the <dir> you are
interested in.  Alternatively, you can reach an e-mail server via
"[e-mail]", to which you can send a message saying "send index
from <dir>"; follow the instructions you receive.

-----------------------------------------------------------------------

Q6.  "Who maintains this FAQ list?"

A:  John W. Gregory
    Applications Department
    Cray Research, Inc.
    Eagan, MN 55121   USA
    [e-mail]
    612-683-3673

This article is Copyright 1994 by John W. Gregory.  It may be freely
redistributed in its entirety provided that this copyright notice is
not removed.  It may not be sold for profit or incorporated in
commercial documents without the written permission of the copyright
holder.  Permission is expressly granted for this document to be made
available for file transfer from installations offering unrestricted
anonymous file transfer on the Internet.

The material in this document does not reflect any official position
taken by Cray Research, Inc.  While all information in this article is
believed to be correct at the time of writing, is it provided "as is"
with no warranty implied.

I've tried to keep my own biases (primarily, toward the high end of
computing) from dominating what I write here, and other viewpoints that
I've missed are welcome.  Suggestions, corrections, topics you'd like
to see covered, and additional material are solicited.

One disclaimer, which I alternately decide I should or shouldn't bother
to state here, is that my wife works for one of the commercial LP firms
mentioned in the LP FAQ.  I don't think you could guess which one,
based on any of my comments in these two FAQs; besides, in my jobs at
Cray and CDC I have had occasion to work with developers of many codes
(and I worked on a few LP codes myself).  At any rate, my wife didn't
write this FAQ, I did.  8v)

This FAQ list is also being posted to news.answers and sci.answers, and
is archived in the periodic posting archive on rtfm.mit.edu
[18.70.0.209], in the anonymous FTP directory /pub/usenet/sci.answers.
The name under which FAQs are archived appears in the Archive-name
line at the top of the article.  This particular FAQ is archived as
"nonlinear-programming-faq".  You will find many other FAQs, covering a
staggering variety of topics, in this hierarchy.  There's a mail
server on that machine, so if you don't have FTP privileges, you can
send an e-mail message to  [e-mail] containing:
    send usenet/sci.answers/nonlinear-programming-faq
as the body of the message.  This FAQ is also cross-posted to
news.answers.

If you wish to cite this FAQ formally (hey, someone actually asked),
you may use:
  Gregory, John W. <[e-mail]> (1994) "Nonlinear Programming FAQ",
  Usenet sci.answers.  Available via anonymous FTP from rtfm.mit.edu
  in /pub/usenet/sci.answers/nonlinear-programming-faq

-----------------------------------------------------------------------
END nonlinear-programming-faq